package com.example.demo.leetcode;

/**
 * 链接 <a href="https://leetcode.cn/problems/reverse-linked-list-ii/?envType=study-plan-v2&envId=top-interview-150">https://leetcode.cn/problems/reverse-linked-list-ii/?envType=study-plan-v2&envId=top-interview-150</a>
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/02/01 16:50
 */
public class _92_反转链表Ⅱ {

    public static void main(String[] args) {
        ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));

        ListNode node2 = new ListNode(3, new ListNode(5));

        ListNode node3 = new ListNode(1, new ListNode(2, new ListNode(3)));
        ListNode node1 = reverseBetween(node2, 1, 2);

        System.out.println();
    }

    /**
     * 思路：
     * 1.先把链表从left到right两个节点截断，一份为三。简称为左边，中间，右边三个部分
     * 2.然后把中间部分的链表反转
     * 3.把左边的尾部指向反转后链表的头部，把中间链表的尾部指向右边链表的头部。
     * <p>
     * <p>
     * <p>
     * 复杂度分析：
     * 时间复杂度：O(n)，最差的情况要遍历链表两次。
     * 空间复杂度: O(right-left+1)
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        //链表为空，或者left和right相等不需要处理
        if (head.next == null || left == right) {
            return head;
        }

        //从left到right两个节点截断，一份为三。简称为左边，中间，右边三个部分
        //中间部分
        ListNode newNode = head;
        //左边的尾节点
        ListNode leftTail = head;
        //右边的头节点
        ListNode rightHead = null;
        //左边从left-1处开始截断
        left = left - 1;

        //遍历的当前节点
        ListNode current = head;
        int index = 1;
        //遍历到right结束
        while (index < right) {
            if (index == left) {
                //当left==index时，把左边尾部的节点指向当前节点
                leftTail = current;
                //再把当前节点的下一个节点，赋值给中间链表的头节点
                newNode = current.next;
            }
            current = current.next;
            index++;
        }
        //把当前节点的下一个节点赋值给右边链表的头节点
        rightHead = current.next;
        //中间链表的尾节点赋值给null
        current.next = null;

        //反转链表

        //中间链表的尾节点的下一个节点指向右边的链表
        ListNode pre = new ListNode();
        pre.next = rightHead;
        //反转链表
        reverse(newNode, pre);

        if (left > 0) {
            //左边链表的尾节点指向中间链表的头节点
            leftTail.next = pre.next;
            return head;
        } else {
            return pre.next;
        }
    }

    /**
     * 反转链表
     *
     * @param head
     * @param pre
     */
    private static void reverse(ListNode head, ListNode pre) {
        while (head != null) {
            ListNode node = new ListNode(head.val);
            node.next = pre.next;
            pre.next = node;

            head = head.next;
        }
    }


    /**
     * 反转链表
     *
     * @param head
     * @param pre
     */
    private void reverse1(ListNode head, ListNode pre) {
        while (head != null) {
            ListNode node = new ListNode(head.val);
            node.next = pre.next;
            pre.next = node;

            head = head.next;
        }
    }


}
